package com.leetcode.算法策略相关.回溯;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author: xiaomi
 * @date: 2021/3/7
 * @description: 131. 分割回文串
 * https://leetcode-cn.com/problems/palindrome-partitioning/
 * 这道题真的难，回溯真是我的短板！
 * 虽然一开始我也想不到用 回溯，只记得可能用 DP，但是又找不到状态方程
 * fo 了，回溯这么难写的吗！
 * 【回文串的结果可以存储，使用 DP 完成预处理！】
 */
public class B_131_分割回文串 {

    static B_131_分割回文串 action = new B_131_分割回文串();

    public static void main(String[] args) {
        test1();
        test2();
        test3();
        test4();
        test5();
    }

    public static void test1() {
        // res = [[a, a, b], [aa, b]]
        String s = "aab";
        List<List<String>> res = action.partition(s);
        System.out.println("res = " + res);
    }

    public static void test2() {
        // res = [[a, b]]
        String s = "ab";
        List<List<String>> res = action.partition(s);
        System.out.println("res = " + res);
    }

    public static void test3() {
        // res = [[a]]
        String s = "a";
        List<List<String>> res = action.partition(s);
        System.out.println("res = " + res);
    }

    public static void test4() {
        // res = [[b, b], [bb]]
        String s = "bb";
        List<List<String>> res = action.partition(s);
        System.out.println("res = " + res);
    }

    public static void test5() {
        // res = [[b, b], [bb]]
        String s = "cdd";
        List<List<String>> res = action.partition(s);
        System.out.println("res = " + res);
    }

    /**
     * 卧蚕我居然写出来了！
     * 虽然效率很低！
     * 接下来考虑哪里优化！
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        List<List<String>> res = new ArrayList<>();

        for (int i = 1; i <= len; i++) {
            //队列用于还原
            ArrayDeque<Integer> deque = new ArrayDeque<>();
            if (isLegal(chars, 0, i)) {
                deque.addLast(i);
                setLocation(chars, deque, i, res, len);
            }
        }
        return res;
    }

    private void setLocation(char[] chars, ArrayDeque<Integer> deque, int index, List<List<String>> res, int len) {
        if (index == len) {
            setList(chars, deque, res);
            return;
        }
        //由于相差1 时肯定是回文串
        deque.addLast(index + 1);
        setLocation(chars, deque, index + 1, res, len);
        deque.removeLast();
        for (int i = index + 2; i <= len; i++) {
            if (isLegal(chars, index, i)) {
                deque.addLast(i);
                setLocation(chars, deque, i, res, len);
                deque.removeLast();
            }
        }
    }

    /**
     * 判断是否构成回文串
     *
     * @param chars
     * @param lastIndex 左边的开始
     * @param index     右边的结束
     * @return
     */
    private boolean isLegal(char[] chars, int lastIndex, int index) {
        if (lastIndex == index || lastIndex == index - 1) {
            return true;
        }
        while (lastIndex < index) {
            if (chars[lastIndex++] != chars[--index]) {
                return false;
            }
        }
        return true;
    }

    private void setList(char[] chars, ArrayDeque<Integer> deque, List<List<String>> res) {
        List<String> list = new ArrayList<>();
        int lastIndex = 0;
        int size = deque.size();
        int count = 0;
        while (count < size) {
            int index = deque.removeFirst();
            list.add(new String(chars, lastIndex, index - lastIndex));
            lastIndex = index;

            deque.addLast(index);
            count++;
        }

        res.add(list);

    }


}
